#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct Node {
	int bf = 0;
	string val;
	Node* left = nullptr;
	Node* right = nullptr;
	Node* parent = nullptr;
};
string sp;
Node* H = nullptr;
void getTree(Node*& h)
{
	string cur;
	cin >> cur;
	if (cur == sp) return;
	h = new Node;
	h->val = cur;
	getTree(h->left); if (h->left) h->left->parent = h;
	getTree(h->right); if (h->right) h->right->parent = h;
}

void post(Node* h, Node* gp)
{
	if (!h) return;

	post(h->left, gp);
	post(h->right, gp);
	cout << h->val << " " << h->bf;
	if (abs(h->bf) > 1) {
		cout << "\nfalse";
		exit(0);
	}
	cout << endl;
}

Node* nextNode(Node* c)
{
	if (c == nullptr) return c;
	if (c->right) {
		c = c->right;
		while (c->left) c = c->left;
		return c;
	}
	while (c->parent && c->parent->right == c) c = c->parent;
	return c->parent;
}

bool jugbst(Node* h)
{
	if (!h) return true;
	Node* cur = h, *next = nullptr;
	while (cur->left) cur = cur->left;
	while (next = nextNode(cur)) {
		if (next->val < cur->val) {
			return false;
		}
		cur = next;
	}
	return true;
}

int getbf(Node* h)
{
	if (!h) return 0;
	int r = getbf(h->right);
	int l = getbf(h->left);
	h->bf = l - r;
	return max(l, r) + 1;
}

int main()
{
	cin >> sp;
	getTree(H);

	if (jugbst(H) == false) {
		cout << "false";
		return 0;
	}
	getbf(H);
    
	post(H, H);
	cout << "true";
    return 0;
}
//    3
//  2        5
//9   4        7
//           6
//       